#include <occmesh/api/chart.h>

int Chart::s_count = 0;

void FaceState::setSetDistance(int set, int distance)
{
    m_setDistances[set] = distance;

    // 判定它到其它特征集的距离是否为零，如果非零就说明它在两个特征集的边界上
    for (size_t i = 0, size = m_setDistances.size(); i < size; i++)
    {
        if (m_setDistances[i] != 0 && i != set)
        {
            m_border = true;
            break;
        }
    }
}

void FaceState::calcDistance()
{
    m_distance = 0;
    for (int d : m_setDistances)
        m_distance += (d * d);

    m_distance = sqrtf(m_distance);
}

bool Chart::contains(const Mesh::FaceHandle &fh) const
{
    return std::find(m_faces.begin(), m_faces.end(), fh) != m_faces.end();
}

bool Chart::add(const Mesh::FaceHandle &fh, float distance)
{
    // 如果已经有这个面，不添加
    if (contains(fh))
        return false;

    m_faces.push_back(fh);

    // 更新最大距离
    m_maxDistance = std::max(m_maxDistance, distance);
    return true;
}

void Chart::merge(const Chart &other)
{
    // 新的图表插入到后面，然后更新距离
    m_faces.insert(m_faces.end(), other.m_faces.begin(), other.m_faces.end());
    m_maxDistance = std::max(m_maxDistance, other.m_maxDistance);
}

void Chart::clear()
{
    m_faces.clear();
    m_maxDistance = 0;
}

ChartBuilder::ChartBuilder(Mesh *mesh, const std::vector<FeatureSet> &sets)
    : m_mesh(mesh), m_featureSets(sets), m_maxDistance(0.0f)
{
    const auto numSets = m_featureSets.size();

    // 添加两个属性，分别储存特征值和状态
    m_mesh->add_property(m_chartBoundaries);
    m_mesh->add_property(m_faceStates);

    // 每个面的距离都初始化为零
    for (auto f_it = m_mesh->faces_begin(), f_end = m_mesh->faces_end(); f_it != f_end; f_it++)
        m_mesh->property(m_faceStates, *f_it) = FaceState(*f_it, numSets);
}

ChartBuilder::~ChartBuilder()
{
    // 完成后移除两个属性
    m_mesh->remove_property(m_chartBoundaries);
    m_mesh->remove_property(m_faceStates);
}

const std::vector<Chart> &ChartBuilder::Build()
{
    std::cout << "Building Charts..." << std::endl;

    initializeDistance();
    buildCharts();

    std::cout << "Charts: " << m_charts.size() << std::endl;

    return m_charts;
}

bool ChartBuilder::Validate()
{
    // 检查是否包含了所有面
    for (auto f_it = m_mesh->faces_begin(), f_end = m_mesh->faces_end(); f_it != f_end; f_it++)
    {
        auto &face = *f_it;
        bool contains = false;
        for (auto &c : m_charts)
        {
            if (c.contains(face))
            {
                contains = true;
                break;
            }
        }

        if (!contains)
            return false;
    }

    return true;
}

void ChartBuilder::initializeDistance()
{
    // 获得特征集数，每个特征集有一个边界
    const auto size = m_featureSets.size();
    std::vector<std::vector<Mesh::FaceHandle>> boundaries(size);

    // 初始化边界集
    for (auto i = 0; i < size; i++)
    {
        // 引用特征集和边界
        const auto &featureSet = m_featureSets.at(i);
        auto &boundary = boundaries[i];

        // 遍历每条特征边
        for (const auto &halfedge : featureSet.halfedges())
        {
            Mesh::VertexHandle vertices[2];

            // 获得起始、终止点
            vertices[0] = m_mesh->to_vertex_handle(halfedge);
            vertices[1] = m_mesh->from_vertex_handle(halfedge);

            for (const auto &vertex : vertices)
            {
                // 考虑顶点的相邻面
                for (auto f_it = m_mesh->vf_begin(vertex), f_end = m_mesh->vf_end(vertex); f_it != f_end; f_it++)
                {
                    const auto &face = *f_it;

                    // 如果这个面不在边界集中，就将其加入
                    if (std::find(boundary.begin(), boundary.end(), face) == boundary.end())
                    {
                        boundary.push_back(face);

                        // 记录这个面的状态：到第 i 个特征集的距离为 1
                        m_mesh->property(m_faceStates, face).setSetDistance(i, 1);
                    }
                }
            }
        }
    }

    // 一开始图表深度是 1，边界边左右各一个面，下一步扩张就得到 2
    int depth = 2;

    // 判定是否修改了边界，循环扩张直到无法修改
    bool modified = true;
    while (modified)
    {
        // 初始化为没有修正
        modified = false;

        // 遍历每个特征集的边界集
        for (auto i = 0; i < boundaries.size(); i++)
        {
            // 考虑其中一个边界集
            auto &boundary = boundaries[i];

            // 存放新边界
            std::vector<Mesh::FaceHandle> newBoundary;
            for (const auto &face : boundary)
            {
                // 判断这个面是否在边界上（这里指它是否在其他边界集扩张的范围内，如果是，就不能扩张到这个面）
                if (m_mesh->property(m_faceStates, face).border())
                    continue;

                // 遍历周围的面
                for (auto f_it = m_mesh->ff_begin(face), f_end = m_mesh->ff_end(face); f_it != f_end; f_it++)
                {
                    auto &state = m_mesh->property(m_faceStates, *f_it);

                    // 如果已经计算出了到当前边界的距离或者已经在边界集中，就跳过
                    if (state.hasSetDistance(i) || std::find(boundary.begin(), boundary.end(), *f_it) != boundary.end())
                        continue;

                    // 获得到当前特征的距离
                    state.setSetDistance(i, depth);
                    newBoundary.push_back(*f_it);
                }
            }

            // 如果新边界是空的，说明这个边界集扩张到极限，直接清空
            boundary.resize(newBoundary.size());

            // 如果新的边界集不是空的，就修改边界
            if (!newBoundary.empty())
            {
                std::copy(newBoundary.begin(), newBoundary.end(), boundary.begin());
                modified = true;
            }
        }

        // 增加深度
        depth++;
    }

    // 计算每个面到所有特征集的平均距离
    for (auto f_it = m_mesh->faces_begin(), f_end = m_mesh->faces_end(); f_it != f_end; f_it++)
    {
        auto &state = m_mesh->property(m_faceStates, *f_it);
        state.calcDistance();

        // 记录最大平均距离
        m_maxDistance = std::max(m_maxDistance, state.distance());
    }
}

void ChartBuilder::initializeSeeds()
{
    // 比较器，用来比较两个面的距离属性
    auto f_compare = [this](const Mesh::FaceHandle &a, const Mesh::FaceHandle &b) -> bool {
        const auto &stateA = m_mesh->property(m_faceStates, a);
        const auto &stateB = m_mesh->property(m_faceStates, b);

        return stateA.distance() < stateB.distance();
    };

    // 处在边界上的面是到所有特征集距离最大的面，将它们按照平均距离由大到小排序
    std::priority_queue<Mesh::FaceHandle, std::vector<Mesh::FaceHandle>, decltype(f_compare)> heap(f_compare);
    for (auto f_it = m_mesh->faces_begin(), f_end = m_mesh->faces_end(); f_it != f_end; f_it++)
        if (m_mesh->property(m_faceStates, *f_it).border())
            heap.push(*f_it);

    // 初始化集合标记
    const auto size = m_featureSets.size();
    std::vector<int> sets(size, 0);

    // 堆中的每个面是一个图表的种子
    while (!heap.empty())
    {
        // 弹出最上面的面（具有最大距离的面）
        auto face = heap.top();
        heap.pop();

        auto &state = m_mesh->property(m_faceStates, face);

        // 如果这个面有一个特征集合 i 没有用过（sets[i] == 0）并且在它的边界上 hasSetDistance(i)
        bool unused = false;
        for (auto i = 0; i < size; i++)
            if (sets[i] == 0 && state.hasSetDistance(i))
                unused = true;

        // 没用过的话
        if (unused)
        {
            // 在“任何特征集”的边界上就对应设为 1，表示它们都用过了这个面
            for (auto i = 0; i < size; i++)
                if (state.hasSetDistance(i))
                    sets[i] = 1;

            // 将这个面分配给当前图表（指定索引就是 m_charts 的大小）
            state.setChart(m_charts.size());

            // 创建一个新图表，将这个面和距离信息加入，作为生成种子
            m_charts.emplace_back(Chart());
            m_charts.back().add(face, state.distance());
        }
    }
}

void ChartBuilder::buildCharts()
{
    // 得到了所有图表的种子
    initializeSeeds();

    // 建立一个比较器，比较拥有给定的两个半边的两个面的距离属性
    auto he_compare = [this](const Mesh::HalfedgeHandle &a, const Mesh::HalfedgeHandle &b) -> bool {
        const auto &stateA = m_mesh->property(m_faceStates, m_mesh->face_handle(a));
        const auto &stateB = m_mesh->property(m_faceStates, m_mesh->face_handle(b));

        return stateA.distance() < stateB.distance();
    };

    // 加载每个图表上一个面的半边
    std::priority_queue<Mesh::HalfedgeHandle, std::vector<Mesh::HalfedgeHandle>, decltype(he_compare)> heap(he_compare);
    for (const auto &chart : m_charts)
    {
        // 取出图表的种子
        const auto face = chart.faces().front();

        // 遍历面上的所有半边，添加到堆中
        for (auto he_it = m_mesh->fh_begin(face), he_end = m_mesh->fh_end(face); he_it != he_end; he_it++)
            heap.push(*he_it);
    }

    // 所有半边都标记为 1
    for (auto e_it = m_mesh->edges_begin(), e_end = m_mesh->edges_end(); e_it != e_end; e_it++)
        m_mesh->property(m_chartBoundaries, *e_it) = 1;

    // 开始循环扩张图表
    while (!heap.empty())
    {
        auto halfedge = heap.top();
        heap.pop();

        auto edge = m_mesh->edge_handle(halfedge);
        auto face = m_mesh->face_handle(halfedge);
        auto faceOpp = (Mesh::FaceHandle)m_mesh->opposite_face_handle(halfedge);

        // 判断半边左右的两个面是否都有效，即处理边界情况
        if (!face.is_valid() || !faceOpp.is_valid())
            continue;

        auto &state = m_mesh->property(m_faceStates, face);
        auto &stateOpp = m_mesh->property(m_faceStates, faceOpp);

        // 如果 face 没有所属图表，就与 faceOpp 交换
        if (!state.hasChart())
        {
            std::swap(face, faceOpp);
            std::swap(state, stateOpp);
        }

        // 如果 faceOpp 没有所属图表
        if (!stateOpp.hasChart())
        {
            // 获得 face 所属图表，将其加入
            auto &chart = m_charts[state.chart()];

            chart.add(faceOpp, stateOpp.distance());
            stateOpp.setChart(state.chart());

            // 然后可以删除这条边
            removeChartBoundaryEdge(edge);

            // 考虑 faceOpp 上的边
            for (auto e_it = m_mesh->fe_begin(faceOpp), e_end = m_mesh->fe_end(faceOpp); e_it != e_end; e_it++)
            {
                auto e = *e_it;

                // 如果这条边仍然被标记为 1，也就是还没有删除，就记录两条半边
                if (m_mesh->property(m_chartBoundaries, e) > 0)
                {
                    heap.push(m_mesh->halfedge_handle(e, 0));
                    heap.push(m_mesh->halfedge_handle(e, 1));
                }
            }
        }
        // 如果两个面属于不同的图表，那么检查距离
        else if (state.chart() != stateOpp.chart())
        {
            auto &chart = m_charts[state.chart()];
            auto &chartOpp = m_charts[stateOpp.chart()];

            // 距离阈值，如果两个 chart 之间的距离小于阈值，就会将它们合并
            const auto epsDistance = m_maxDistance / 4;
            if ((chart.maxDistance() - state.distance()) < epsDistance &&
                (chartOpp.maxDistance() - state.distance()) < epsDistance)
                mergeCharts(chart, chartOpp);
        }
    }

    // 将空的图表移动到末端
    auto move = [](const Chart &chart) { return chart.cleared() || chart.faces().empty(); };
    auto last = std::remove_if(m_charts.begin(), m_charts.end(), move);

    // 删除第一个空图表到末端之间的空图表
    m_charts.erase(last, m_charts.end());

    // 保存图表顶点
    for (auto &chart : m_charts)
    {
        auto &faces = chart.faces();
        auto &vertices = chart.vertices();
        for (auto &face : faces)
        {
            auto fv_iter = m_mesh->fv_begin(face), fv_end = m_mesh->fv_end(face);
            for (; fv_iter != fv_end; fv_iter++)
                vertices.push_back(*fv_iter);
        }

        // 删除重复顶点
        std::sort(vertices.begin(), vertices.end());
        vertices.erase(std::unique(vertices.begin(), vertices.end()), vertices.end());
    }
}

bool ChartBuilder::removeChartBoundaryEdge(Mesh::EdgeHandle edge)
{
    // 已经被删除就不用删除
    if (m_mesh->property(m_chartBoundaries, edge) == 0)
        return false;

    // 设为零，表示删除边
    m_mesh->property(m_chartBoundaries, edge) = 0;

    // 获得边上的半边
    auto halfedge = m_mesh->halfedge_handle(edge, 0);

    // 获得两个端点
    Mesh::VertexHandle vertices[2];
    vertices[0] = m_mesh->to_vertex_handle(halfedge);
    vertices[1] = m_mesh->from_vertex_handle(halfedge);

    // 查找周围的边，删除没有连接到 2 个其它边界边的边
    // 这个递归过程将会持续进行，直到检查完整个边界边集
    for (const auto &vertex : vertices)
    {
        for (auto e_it = m_mesh->cve_begin(vertex), e_end = m_mesh->cve_end(vertex); e_it != e_end;)
        {
            // 每删除一个这样的边，就回到开头重新遍历，确保全部删除
            if (!checkChartBoundaryEdge(*e_it) && removeChartBoundaryEdge(*e_it))
                e_it = m_mesh->cve_begin(vertex);
            else
                e_it++;
        }
    }

    return true;
}

bool ChartBuilder::checkChartBoundaryEdge(Mesh::EdgeHandle edge)
{
    // 删除的边不属于边界
    if (m_mesh->property(m_chartBoundaries, edge) == 0)
        return false;

    // 获得边上的半边
    auto halfedge = m_mesh->halfedge_handle(edge, 0);

    // 获得两个端点
    Mesh::VertexHandle vertices[2];
    vertices[0] = m_mesh->to_vertex_handle(halfedge);
    vertices[1] = m_mesh->from_vertex_handle(halfedge);

    // 检查当前边连接了多少个其它边界边
    int connections = 0;
    for (const auto &vertex : vertices)
    {
        for (auto e_it = m_mesh->cve_begin(vertex), e_end = m_mesh->cve_end(vertex); e_it != e_end; e_it++)
        {
            // 一旦连接到其它边界边，退出循环
            if (*e_it != edge && m_mesh->property(m_chartBoundaries, *e_it) > 0)
            {
                connections++;
                break;
            }
        }
    }
    // 只有两个顶点，因此 connections = 0, 1, 2

    // 判断连接数是否为 2
    return connections == 2;
}

void ChartBuilder::mergeCharts(Chart &chartTo, Chart &chartFrom)
{
    // 确保合并两个非空图表
    assert(!chartTo.cleared());
    assert(!chartFrom.cleared());

    // 取目标图表的面，获得它所属的图表索引
    const auto &faceRef = chartTo.faces().front();
    auto chartIndex = m_mesh->property(m_faceStates, faceRef).chart();

    // 修改源图表中的面所属的图表
    for (const auto &f : chartFrom.faces())
        m_mesh->property(m_faceStates, f).setChart(chartIndex);

    chartTo.merge(chartFrom);
    chartFrom.clear();
}